package OptimalAlgorithm.PrefixSum;
//给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
//子数组是数组中元素的连续非空序列。
//eg:
//输入：nums = [1,1,1], k = 2
//输出：2

import java.util.HashMap;

public class SubarraySum {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int n = nums.length;
        int sum = 0;
        int ret = 0;
        map.put(0, 1);
        //初始化 map.put(0, 1) 是为了正确统计从数组开头（索引 0）到当前位置的子数组。
        // 这类子数组的和等于 k 时，其对应的前缀和差为 sum - 0 = k，必须通过提前存入 0:1 才能被计数。
        for (int i = 0; i < n; i++) {
            sum += nums[i];//求前缀和
            ret += map.getOrDefault(sum - k,0);//在i之前 前缀和等于sum - k 的次数（从map中找） -> 也就说明在i之前出现多少个子数组和为k
            map.put(sum, map.getOrDefault(sum,0) + 1);//将当前i下标的前缀和放入map中
        }
        return ret;
    }
}
